/**
 * 69. Sqrt(x)
 * https://leetcode.com/problems/sqrtx/
 */
package lc69;

public class Main {
  public static void main(String[] args) {
    // int x = 2147395599;
    int x = 2147483647;
    System.out.println(new Solution().mySqrt(x));
  }
}

class Solution {
  public int mySqrt(int x) {
    if (x == 0) return 0;
    if (x < 4) return 1;
    int m = x / 2;
    while (true) {
      if (m > Math.sqrt(Integer.MAX_VALUE)) m = (int)Math.sqrt(Integer.MAX_VALUE);
      int s = m * m;
      if (s > x) m /= 2;
      if (s == x) return m;
      if (s < x) {
        if (m == (int)Math.sqrt(Integer.MAX_VALUE)) return (int)Math.sqrt(Integer.MAX_VALUE);
        m++;
        if (m * m > x) return m - 1;
      }
    }
  }
}
